BLAKE (хеш-функция)

BLAKE — криптографическая хеш-функция, в разработке которой принимали участие Жан-Филипп Омассон (Jean-Philippe Aumasson), Лука Хенцен (Luca Henzen), Вилли Майер (Willi Meier), Рафаэль Фан (Raphael C.-W. Phan).

Существуют два варианта хеш-функции: BLAKE-256 и BLAKE-512.

История

Впервые BLAKE была представлена на конкурсе криптографических алгоритмов, который проводился Национальным институтом стандартов и технологий США (англ. NIST hash function competition, рус. SHA-3 (конкурс)). BLAKE стала одним из пяти финалистов конкурса (англ. финалисты).

Криптостойкость

Хеш-функция BLAKE построена из трёх ранее изученных компонентов:

• режим итерации HAIFA обеспечивает стойкость к атакам второго рода
• внутренняя структура local wide-pipe обеспечивает защиту от коллизий
• алгоритм сжатия для BLAKE является модифицированной версией хорошо параллелизируемого поточного шифра ChaCha, чья безопасность тщательно проанализирована

Быстродействие и реализация

Быстродействие на двух различных процессорах:

Процессор	Скорость (тактов/байт)
	BLAKE-256	BLAKE-512
Intel Core i5-2400M (Sandy Bridge), Q1 2011	7,49	5,64
AMD FX-8120 (Bulldozer), Q4 2011	11,83	6,88

Возможность реализации на различных микроконтроллерах:

Микроконтроллер	BLAKE-256		BLAKE-512
	RAM(байт)	ROM(байт)	RAM(байт)	ROM(байт)
Cortex-M3 based microcontroller (32-bit processor)	280	1320	516	1776
ATmega1284P microcontroller (8-bit processor)	267	3434	525	6350

Быстродействие на ППВМ (англ. FPGA):

На ППВМ Xilinx Virtex 5 BLAKE-256 реализуется на 56 ячейках и может достигать пропускной способности более чем в 160 Мбит/с, а BLAKE-512 — на 108 ячейках и со скоростью до 270 Мбит/с.

Быстродействие на ASIC:

На 180nm ASIC, BLAKE-256 может быть реализована на 13.5 kGE. На 90nm ASIC BLAKE-256 реализована на 38 kGE и может достигать производительности в 10 Гбит/с, а BLAKE-512 — на 79 kGE и со скоростью 15 Гбит/с.

Алгоритм

Как упоминалось ранее, хеш-функция BLAKE построена из трёх ранее изученных компонентов:

• режим итерации HAIFA
• внутренняя структура local wide-pipe
• алгоритм сжатия для BLAKE, является модифицированной версией хорошо параллелизируемого поточного шифра ChaCha, чья безопасность тщательно проанализирована.

Рассмотрим алгоритм BLAKE-256

BLAKE-256 оперирует с 32-битными словами и возвращает 32-байтный хеш.

Константы

Существуют начальные константы, т. н. INITIAL VALUES (IV):

IV0 = 6A09E667 IV1 = BB67AE85
IV2 = 3C6EF372 IV3 = A54FF53A
IV4 = 510E527F IV5 = 9B05688C
IV6 = 1F83D9AB IV7 = 5BE0CD19

16 констант (первые цифры числа пи):

c0  = 243F6A88  c1  = 85A308D3
c2  = 13198A2E  c3  = 03707344
c4  = A4093822  c5  = 299F31D0
c6  = 082EFA98  c7  = EC4E6C89
c8  = 452821E6  c9  = 38D01377
c10 = BE5466CF  c11 = 34E90C6C
c12 = C0AC29B7  c13 = C97C50DD
c14 = 3F84D5B5  c15 = B5470917 

перестановки {0,…,15} (используются во всех функциях BLAKE):

σ0 =  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
σ1 = 14 10  4  8  9 15 13  6  1 12  0  2 11  7  5  3
σ2 = 11  8 12  0  5  2 15 13 10 14  3  6  7  1  9  4
σ3 =  7  9  3  1 13 12 11 14  2  6  5 10  4  0 15  8
σ4 =  9  0  5  7  2  4 10 15 14  1 11 12  6  8  3 13
σ5 =  2 12  6 10  0 11  8  3  4 13  7  5 15 14  1  9
σ6 = 12  5  1 15 14 13  4 10  0  7  6  3  9  2  8 11
σ7 = 13 11  7 14 12  1  3  9  5  0 15  4  8  6  2 10
σ8 =  6 15 14  9 11  3  0  8 12  2 13  7  1  4 10  5
σ9 = 10  2  8  4  7  6  1  5 15 11  9 14  3 12 13  0

Функции сжатия

Функция сжатия алгоритма BLAKE-256 принимает на вход:

• Переменные цепочки h = h₀,…,h₇ (8 слов);
• Блок сообщения m = m₀,…,m₁₅;
• Значение соли s = s₀,…,s₃;
• Значение счётчика t = t₀,t₁.

Таким образом, на вход ей подаётся 30 слов (8+16+4+2=30, 30*4 = 120 байт = 960 бит). Возвращает функция сжатия только новое значение переменных цепочки: h' = h'₀,…,h'₇. В дальнейшем будем обозначать h'=compress(h, m, s, t).

Инициализация

16 переменных, v₀,…,v₁₅, описывающих текущее состояние v, инициализируются начальными значениями в зависимости от входных данных и представлены в виде матрицы 4×4:

${\begin{pmatrix}v_{0}&v_{1}&v_{2}&v_{3}\\v_{4}&v_{5}&v_{6}&v_{7}\\v_{8}&v_{9}&v_{10}&v_{11}\\v_{12}&v_{13}&v_{14}&v_{15}\\\end{pmatrix}}$←${\begin{pmatrix}h_{0}&h_{1}&h_{2}&h_{3}\\h_{4}&h_{5}&h_{6}&h_{7}\\s_{0}\oplus c_{0}&s_{1}\oplus c_{1}&s_{2}\oplus c_{2}&s_{3}\oplus c_{3}\\t_{0}\oplus c_{4}&t_{0}\oplus c_{5}&t_{1}\oplus c_{6}&t_{1}\oplus c_{7}\\\end{pmatrix}}$

Раундовая функция

После того, как состояние v инициализировано, запускается серия из 14 раундов. Раунд — это операция над состоянием $v$, которая производит вычисления, разбитые на следующие блоки:

G0(v0, v4, v8 , v12) G1(v1, v5, v9 , v13) G2(v2, v6, v10, v14) G3(v3, v7, v11, v15) 
G4(v0, v5, v10, v15) G5(v1, v6, v11, v12) G6(v2, v7, v8 , v13) G7(v3, v4, v9 , v14)   

на r-м раунде блок вычислений $G_{i}(a,b,c,d)$ работает следующим образом:

Графическая иллюстрация работы блока вычислений Gi

j ← σr%10[2×i]
k ← σr%10[2×i+1]
a ← a + b + (mj ⊕ ck)  
d ← (d ⊕ a) >>> 16
c ← c + d                  
b ← (b ⊕ c) >>> 12
a ← a + b + (mk ⊕ cj)  
d ← (d ⊕ a) >>> 8
c ← c + d                   
b ← (b ⊕ c) >>> 7

Column step and diagonal step of BLAKE-256 hash function algorythm

Первые четыре блока G₀,…,G₃ могут вычисляться параллельно, так как каждый изменяет свою определённую колонку переменных матрицы состояний. Назовём процедуру вычисления G₀,…,G₃ column step. Точно так же могут быть параллельно вычислены G₄,…,G₇, но они в свою очередь изменяют каждый свою диагональ матрицы состояния v. Поэтому назовём процедуру вычисления G₄,…,G₇ diagonal step. Возможность параллельного вычисления G_i представлена графически.

На раундах, номера r которых больше 9, используется перестановка σ_r%10, например на 13-м раунде используется σ₃.

Последний шаг

После всех раундов новое значение переменных цепочки h'₀,…,h'₇ вычисляется из переменных $v_{0},...,v_{15}$ матрицы состояния, входных переменных $h$ и из соли $s$:

h'0 ← h0 ⊕ s0 ⊕ v8
h'1 ← h1 ⊕ s1 ⊕ v9
h'2 ← h2 ⊕ s2 ⊕ v10
h'3 ← h3 ⊕ s3 ⊕ v11
h'4 ← h4 ⊕ s4 ⊕ v12
h'5 ← h5 ⊕ s5 ⊕ v13
h'6 ← h6 ⊕ s6 ⊕ v14
h'7 ← h7 ⊕ s7 ⊕ v15

Хеширование сообщения

Опишем процесс хеширования сообщения m длиной l<2^64 бит. Сначала сообщение дополняется функцией padding данными для кратности 512 битам (64 байтам), затем, блок за блоком, его обрабатывает функция сжатия compression function.

В функции padding сообщение сначала дополняется битами, так, что его длина становится по модулю 512 равной 447: сначала добавляется 1, затем необходимое количество нолей. После этого прибавляется ещё одна 1 и 64-битное представление длины сообщения l от старшего бита к младшему. Таким образом, длина сообщения становится кратной 512. Padding гарантирует, что длина сообщения станет кратной 512 битам.

Чтобы высчитать хеш сообщения, результат функции padding делится на блоки из 16 слов m₀,…,m_N-1. Пусть L_i — количество бит исходного сообщения в блоках m₀,…,m_i, то есть исключая те биты, которые были добавлены в процедуре padding. Например, если сообщение имеет длину 600 бит, то после процедуры padding оно будет иметь длину 1024 бита и будет разделено на два блока: m₀ и m₁. Притом L₀=512, L₁=600. В некоторых случаях последний блок не содержит бит оригинального сообщения. Например, если в исходном сообщении 1020 бит, то в результате процедуры padding оно будет иметь длину 1536 бит и в m₀ будет 512 бит исходного сообщения, в m₁ — 508, а в m₂ — 0. Выставим L₀=512, L₁=1020, а L₂=0. То есть правило следующее: если в последнем блоке нет бит оригинального сообщения, то выставим счётчик L_N-1 равным 0. Это гарантирует, что если i ≠ j, то L_i ≠ L_j. Значение соли определяется пользователем или задаётся равным 0, если её не нужно использовать (s₀=s₁=s₂=s₃=0). Хеш сообщения таким образом вычисляется:

h0 ← IV
for i=0,...,N-1
   hi+1 ← compress(hi,mi,s,li)
return hN.

Процесс хеширования представлен наглядно на блок-схеме:

Алгоритм 64-битной версии функции идентичен: значения сдвига равны 32, 25, 16 и 11 соответственно, число раундов увеличено до 16.

Отличия от quarterround алгоритма ChaCha

• Добавление констант к сообщению.
• Изменённое направление сдвига.

Хеши BLAKE

BLAKE-512("")
 = A8CFBBD73726062DF0C6864DDA65DEFE58EF0CC52A5625090FA17601E1EECD1B
   628E94F396AE402A00ACC9EAB77B4D4C2E852AAAA25A636D80AF3FC7913EF5B8

BLAKE-512("The quick brown fox jumps over the lazy dog")
 = 1F7E26F63B6AD25A0896FD978FD050A1766391D2FD0471A77AFB975E5034B7AD
   2D9CCF8DFB47ABBBE656E1B82FBC634BA42CE186E8DC5E1CE09A885D41F43451

BLAKE2

BLAKE2 (Сайт BLAKE2) — это улучшенная версия BLAKE — одного из пяти финалистов конкурса на хеш-функцию SHA-3 (главным образом улучшено быстродействие), представлена 21 декабря 2012 года. Разработчики: Jean-Philippe Aumasson, Samuel Neves, Zooko Wilcox-O'Hearn, и Christian Winnerlein. Была создана как альтернатива широко использовавшимся в прошлом MD5 и SHA-1, в которых были найдены уязвимости.

Отличия от BLAKE

В BLAKE2, в отличие от BLAKE, нет добавления констант в раундовой функции. Также изменены константы сдвига, упрощено добавление, добавлен блок параметров, который складывается с инициализирующими векторами. Кроме того, сокращено число раундов с 16 до 12 у функции BLAKE2b (аналог BLAKE-512) и с 14 до 10 у BLAKE2s (аналог BLAKE-256). В результате число тактов на бит сократилось с 7,49 для BLAKE-256 и 5,64 для BLAKE-512 до 5,34 и 3,32 для Blake2s и Blake2b соответственно.

Хеши BLAKE2

BLAKE2b-512("")
 = 786A02F742015903C6C6FD852552D272912F4740E15847618A86E217F71F5419
   D25E1031AFEE585313896444934EB04B903A685B1448B755D56F701AFE9BE2CE

BLAKE2b-512("The quick brown fox jumps over the lazy dog")
 = A8ADD4BDDDFD93E4877D2746E62817B116364A1FA7BC148D95090BC7333B3673
   F82401CF7AA2E4CB1ECD90296E3F14CB5413F8ED77BE73045B13914CDCD6A918

BLAKE2s-256("")

= 69217A3079908094E11121D042354A7C1F55B6482CA1A51E1B250DFD1ED0EEF9



BLAKE2s-256("The quick brown fox jumps over the lazy dog")

= 606BEEEC743CCBEFF6CBCDF5D5302AA855C256C29B88C8ED331EA1A6BF3C8812



BLAKE2s-128("")

= 64550D6FFE2C0A01A14ABA1EADE0200C



BLAKE2s-128("The quick brown fox jumps over the lazy dog")

= 96FD07258925748A0D2FB1C8A1167A73

Литература

Eli Biham and Orr Dunkelman. A framework for iterative hash functions - HAIFA. — ePrint, 2007. — 207 с.

Ссылки

• Сайт BLAKE
• Сайт BLAKE2
• Исходный код на VHDL, разработанный Группой Исследователей в Области Криптографии университета Джорджа Мейсона